package com.bang.study.day01;

import com.bang.study.util.ArrayUtil;
import com.bang.study.util.TestUtil;
import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;


/**
 * @Auther: Bang
 * @Date: 2019/9/21 0021 10:18
 * @Description: 希尔排序
 * @描述:
 *      先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。具体算法描述如下：
 *     1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 *     2. 按增量序列个数k，对序列进行k 趟排序；
 *     3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，
 *        分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，
 *        表长度即为整个序列的长度。
 *
 * @算法分析:
 *          最佳情况：T(n) = O(nlog2 n)  最坏情况：T(n) = O(nlog2 n)  平均情况：T(n) =O(nlog2n)　
 *          希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，
 *          也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
 *          它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
 *          希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
 *          每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
 *
 * @工作原理:
 *         希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
 *         随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，
 *         整个文件恰被分成一组，算法便终止
 */
public class ShellSort {

    /**
     * gap=1 初始值
     * gap = gap * 3 +1 A003462 性能相较于length/2好一点
     *
     * @param arr
     */
    public static void sort(Integer[] arr) {
        int length = arr.length;
        int gap = 1;
        while ((gap * 3 + 1) < length) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int curr = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > curr) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex = preIndex - gap;
                }
                //  将curr放到找到的元素的下一个位置
                arr[preIndex + gap] = curr;
            }
            gap = (gap - 1) / 3;
        }

    }

    public static void sortGap(Integer[] arr) {
        int length = arr.length;
        long startTime = System.nanoTime();
        int gap = length / 2;
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int curr = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > curr) {
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex = preIndex - gap;
                }
                //  将curr放到找到的元素的下一个位置
                arr[preIndex + gap] = curr;
            }
            gap = gap / 2;
        }
        long endTime = System.nanoTime();
        double time = (endTime - startTime) / 1000000000.0;
        System.out.println(String.format("ShellSort sortGap 消耗时间: %s S ,数据量: %s", time, length));

    }

    public static void main(String[] args) {
        Integer[] array = ArrayUtil.generateRandomArray(1000000, 0, 1000000);
        Integer[] newArr = Arrays.copyOf(array, array.length);
        System.out.println(array==newArr);
        ArrayUtil.printArray(array, 10);
//        TestUtil.test(ShellSort.class,newArr);
        sortGap(array);
        ArrayUtil.printArray(array, 10);

    }
}
